package com.hankz.cc.leetcode;

import java.util.*;

/**
 * @auther zzc
 * @date 2021/4/1 15:17
 */
public class 前k个高频元素 {

    //堆   哈希表
    public List<Integer> topKNums(int[] nums, int k) {
        List result = getResult(nums, k);
        return result;
    }

    private List getResult(int[] nums, int k) {
        //     key:nums里的元素    valus：元素出现的次数
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                map.put(nums[i], map.get(nums[1]) + 1);
            } else {
                map.put(nums[i], 1);
            }
        }
        //遍历map  用最小堆存频率最大的前k个元素
        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer a, Integer b) {
                return map.get(a) - map.get(b);
            }
        });
        for (Integer key : map.keySet()) {
            if (queue.size() < k) {
                queue.add(key);
            } else if (map.get(key) > map.get(queue.peek())) {
                //如果遍历到的元素次数大于最小堆的顶点   则替换
                queue.remove();
                queue.add(key);
            }
        }
        //取出最小堆中的元素
        List<Integer> res = new ArrayList<>();
        while (!queue.isEmpty()) {
            res.add(queue.remove());
        }
        return res;
    }

    //桶排序


}
